#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct LinkNode
{
    struct LinkNode *next;
    int data;
} LinkNode_t, *LinkNode_p;

typedef struct LinkQueue
{
    int size;
    LinkNode_p front;
    LinkNode_p rear;
} LinkQueue_t, *LinkQueue_p;

LinkQueue_p LinkQueue_init()
{
    LinkQueue_p queue = (LinkQueue_p)malloc(sizeof(LinkQueue_t));
    queue->size = 0;
    queue->front = queue->rear = (LinkNode_p)malloc(sizeof(LinkNode_t));
}

void enQueue(LinkQueue_p queue, int data)
{
    LinkNode_p node = (LinkNode_p)malloc(sizeof(LinkNode_t));
    node->data = data;
    node->next = NULL;
    if (queue->size == 0)
    {
        queue->front->next = node;
        queue->rear = node;
    }
    else
    {
        queue->rear->next = node;
        queue->rear = node;
    }
    queue->size++;
}

int deQueue(LinkQueue_p queue)
{
    int data = -1;
    if (queue->size == 0)
    {
        printf("Queue is empty!\n");
        return data;
    }
    else if (queue->size == 1)
    {
        data = queue->front->next->data;
        free(queue->front->next);
        queue->front->next = NULL;
    }
    else
    {
        data = queue->front->next->data;
        LinkNode_p currNode = queue->front->next;
        queue->front->next = currNode->next;
        free(currNode);
    }
    queue->size--;
    return data;
}

void traverse(LinkQueue_p queue)
{
    LinkNode_p currNode = queue->front->next;
    while (currNode != NULL)
    {
        printf("%d ", currNode->data);
        currNode = currNode->next;
    }
    printf("\n");
}

int main()
{
    LinkQueue_p q1 = LinkQueue_init();
    enQueue(q1, 1);
    enQueue(q1, 2);
    enQueue(q1, 3);
    enQueue(q1, 4);
    traverse(q1);
    printf("%d\n", deQueue(q1));
    traverse(q1);
}